package com.lun.easy;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.lun.util.NAryTree.Node;

public class NAryTreePreorderTraversal {
    
	//方法一：递归法
	public List<Integer> preorder(Node root) {
        List<Integer> result = new ArrayList<>();
        preorder(root, result);
        return result;
    }
    
    private void preorder(Node root, List<Integer> result) {
    	if(root == null)
    		return;
    	
    	result.add(root.val);
    	
    	if(root.children != null)
    		for(Node node : root.children)
    			preorder(node, result);
    }
    
    //方法二：迭代法
    public List<Integer> preorder2(Node root) {
    	List<Integer> result = new ArrayList<>();
    	
    	if(root == null)
    		return result;
    	
    	LinkedList<Node> stack = new LinkedList<>();
    	stack.push(root);
    	
    	while(!stack.isEmpty()) {
    		Node node = stack.pop();
    		result.add(node.val);
    		
    		if(node.children != null)
    			stack.addAll(0, node.children);
    	}
    	
    	return result;
    }
    
}
